package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;

import java.util.*;

/**
 * https://leetcode.com/problems/redundant-connection/description/
 * <p>
 * 并查集
 *
 * @author tzp
 * @since 2020/11/2
 */
public class LC684_1 extends LC547_1 implements GraphProblem {
    static class UF {
        int[] parent;
        int[] rank;

        public UF(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];//find的时候进行压缩path
                x = parent[x];
            }
            return x;
        }

        public boolean union(int x, int y) {
            int xp = find(x);
            int yp = find(y);
            if (xp == yp) return false;
            if (rank[xp] < rank[yp]) {//xprank小, 把xp接到yp下面
                parent[xp] = yp;
            } else if (rank[xp] > rank[yp]) {
                parent[yp] = xp;
            } else {//==, rank+1
                parent[xp] = yp;
                rank[yp]++;
            }
            return true;
        }
    }

    //在树的基础上多连了一条边, 则边的个数等于节点数
    public int[] findRedundantConnection(int[][] edges) {
        UF uf = new UF(edges.length + 1);//1base
        for (int i = 0; i < edges.length; i++) {
            if (uf.find(edges[i][0]) == uf.find(edges[i][1])) {//已经连上了
                return edges[i];
            } else {
                uf.union(edges[i][0], edges[i][1]);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC684_1()
//                .findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}})));
                .findRedundantConnection(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}})));
    }
}
